<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    //封装哈希表类
    function HashTable(){
        // 属性
        this.storage = []
        this.count = 0
        this.limit = 7

        // 方法
        // 哈希函数
       HashTable.prototype.hashFunc= function (str,size) {
            // 定义储存变量
            var count = 0;
            for (var i=0;i<str.length;i++){
                // 获取对应unicode码
                // 霍纳法则
                count = count * 37 + str.charCodeAt(i);
            }
            var index = count % size;

            return index;
        }
        // 插入&更新操作
        HashTable.prototype.put = function (key,value) {
            // 1.根据key获取对应的index
            var index = this.hashFunc(key,this.limit)

            // 2.根据index取出对应的bucket
            var bucket = this.storage[index]

            // 3.判断该bucket是否为空
            if(bucket == null){
                bucket = []
                this.storage[index] = bucket
            }

            // 4.判断是否是修改数据
            for(var i = 0; i < bucket.length; i++){
                var tuple = bucket[i];
                if(tuple[0] == key){
                    tuple[1] = value
                    return
                }
            }

            // 5.添加数据
            bucket.push([key,value])
            this.count += 1

            // 6.判断是否需要扩容操作
            if(this.count > this.limit * 0.75){
                var newSize = this.limit * 2;
                var newPrime = this.getPrime(newSize)
                this.resize(newPrime)
            }

        }
        // 获取操作
        HashTable.prototype.get = function (key) {
              // 1.获取对应下标值
               var index = this.hashFunc(key,this.limit)

              // 2.获取对应bucket
               var bucket = this.storage[index];

              // 3.判断bucket是否为空
                if(bucket == null){
                    return null
                }

              // 4.有bucket进行线性查找
               for(var i=0; i<bucket.length;i++){
                   var tuple = bucket[i];
                   if(tuple[0] == key){
                      return tuple[1]
                   }
               }

               // 5.没有找到返回null
                return  null
        }
        // 删除操作
        HashTable.prototype.delete = function (key) {
            // 1.获取对应下标值
            var index = this.hashFunc(key,this.limit)

            // 2.获取对应bucket
            var bucket = this.storage[index];

            // 3.判断bucket是否为空
            if(bucket == null){
                return null
            }

            // 4.有bucket进行线性查找
            for(var i=0; i<bucket.length;i++){
                var tuple = bucket[i];
                if(tuple[0] == key){
                    bucket.splice(i,1)
                    this.count--
                    //缩小容量
                    if(this.limit > 7 && this.count * this.limit * 0.25){
                           var newSize = Math.floor(this.limit / 2)
                           var newPrime = this.getPrime(newSize)
                           this.resize(newPrime)
                    }
                    return tuple[1]
                }
            }

            // 5.没有找到返回null
            return  null
        }
        //表扩容
        HashTable.prototype.resize = function (newLimit) {
            // 1.保存旧的数组内容
             var oldStorage = this.storage

            // 2.重置所有的属性
            this.storage = [];
            this.count = 0;
            this.limit = newLimit

            // 3.遍历oldStorage
            for(var i = 0; i < oldStorage.length; i++){
                // 3.1取出对应的bucket
                var bucket = oldStorage[i]

                // 3.2判断是否为空
                if(bucket == null){
                    continue
                }

                // 3.3bucket中有数据,那么取出数据,然后插入
                for(var j = 0; j < bucket.length; j++){
                    var tuple = bucket[j]
                    this.put(tuple[0],tuple[1])
                }
            }
        }
        //判断是否是质数
        HashTable.prototype.isPrime = function (num) {

            var temp = parseInt(Math.sqrt(num))

            for (var i=2; i<=temp; i++){

                if(num % i == 0){

                    return false
                }
            }

            return true;

        }

        // 获取质数方法
        HashTable.prototype.getPrime = function (num) {

                while (!this.isPrime(num)){
                    num++
                }
                return num
        }
    }
</script>
</body>
</html>